package alg;

import java.util.Random;

public class TrueDyn {

	private int n;
	private byte[][] adjacency;
	private long[][] ImB;
	private long[][][] inverse;
	private int mode;
	private long p;
	private long det;
	private int trans;
	private Random rand;
	
	/*
	private long ImB(int i, int j)
	{
		long k = 0;
		if (i == j)
			k = 1;
		
		return Math.minmod(k, B[i][j], p);
	}
	*/
	
	public TrueDyn(int size)
	{
		//int seed = 4123;
		//int seed = 1234;
		rand = new Random();
		n = size;
		adjacency = new byte[n][n];
		inverse = new long[n][n][2];
		mode = 0;
		ImB = new long[n][n];
		p = 2147483647;
		det = 1;
		trans = n;
		for (int i=0; i<n; i++)
		{
			adjacency[i][i] = 1;
			inverse[i][i][mode] = 1;
			ImB[i][i] = 1;
		}
	}
	
	public void insert(int i, int j)
	{
		if (adjacency[i][j] != 1)
		{
			long r = rand.nextInt((int)p-1)+1;
			update(i,j,r);
		}
		adjacency[i][j] = 1;
	}
	
	public void delete(int i, int j)
	{
		if (i == j)
			return;
		
		//System.out.println("i="+i+" j="+j+" adjacency="+adjacency[i][j]);
		if (adjacency[i][j] != 0)
		{
			update(i,j,0);
		}
		adjacency[i][j] = 0;
	}
	
	private void update(int i, int j, long val)
	{
		//long v = Math.minmod(val, ImB[i][j], p);
		long v = val;
		if (val == 0)
			v = p - ImB[i][j];
		
		//long Bb = Math.addmod(1, Math.multmod(v,inverse[j][i],p), p);
		long Bb = (1+(v*inverse[j][i][mode]))%p;
		if (Bb == 0)
		{
			System.out.println("Warning: Bb == 0");
			if (val == 0)
				throw new RuntimeException("determinant became 0 during delete");
			
			long r = rand.nextInt((int)p-1)+1;
			update(i,j,r);
			return;
		}
		ImB[i][j] = val;
		//long[][] newInv = new long[n][n];
		trans = 0;
		long Bbinv = Math.inv(Bb, p);
		for (int k=0; k<n; k++)
		{
			for (int h=0; h<n; h++)
			{
				/*
				long calc = Math.multmod(inverse[k][i], inverse[j][h], p);
				calc = Math.multmod(calc, v, p);
				calc = Math.divmod(calc, Bb, p);
				*/
				long calc = (((inverse[k][i][mode] * inverse[j][h][mode])%p) * ((v * Bbinv)%p))%p;
				calc = Math.minmod(inverse[k][h][mode], calc, p);
				inverse[k][h][mode ^ 1] = calc;
				if (calc != 0)
					trans++;
			}
		}
		mode = mode ^ 1;
		
		//det = Math.multmod(det,Bb,p);
	}
	
	/*private long adj(int i, int j)
	{
		return Math.multmod(det, inverse[i][j], p);
	}*/
	
	private boolean existsPath(int i, int j)
	{
		//System.out.println("LOLOL");
		return inverse[i][j][mode] != 0;
	}
	
	public int countTrans()
	{
		/*
		int c = 0;
		for (int i=0; i<n; i++)
		{
			for (int j=0; j<n; j++)
			{
				if (existsPath(i,j))
					c++;
					
				//System.out.println("LOL");
			}
		}
		return c;
		*/
		return trans;
	}
	
	public void printInverse()
	{
		for (int k=0; k<n; k++)
		{
			for (int h=0; h<n; h++)
			{
				System.out.print("["+inverse[k][h]+"]");
			}
			System.out.println();
		}
	}
	
	/*
	public void printB()
	{
		for (int k=0; k<n; k++)
		{
			for (int h=0; h<n; h++)
			{
				System.out.print("["+B[k][h]+"]");
			}
			System.out.println();
		}
	}
	*/
	
	public void printIMB()
	{
		for (int k=0; k<n; k++)
		{
			for (int h=0; h<n; h++)
			{
				System.out.print("["+ImB[k][h]+"]");
			}
			System.out.println();
		}
	}
	
	public void printDeterminant()
	{
		System.out.println("det="+det);
	}
}
